home *** CD-ROM | disk | FTP | other *** search
/ Czech Logic, Card & Gambling Games / Logické hry.iso / hry / Fish Fillets / script / share / prog_finder.lua < prev    next >
Encoding:
Text File  |  2005-07-16  |  2.8 KB  |  101 lines
  1.  
  2. dir_no = 0
  3. dir_up = 1
  4. dir_down = 2
  5. dir_left = 3
  6. dir_right = 4
  7.  
  8. -- -----------------------------------------------------------------
  9. function getDirShift(dir)
  10.     local shiftX, shiftY = 0, 0
  11.     if dir == dir_left then
  12.         shiftX = -1
  13.     elseif dir == dir_right then
  14.         shiftX = 1
  15.     elseif dir == dir_up then
  16.         shiftY = -1
  17.     elseif dir == dir_down then
  18.         shiftY = 1
  19.     end
  20.     return shiftX, shiftY
  21. end
  22.  
  23. -- -----------------------------------------------------------------
  24. local function isFreePlace(model, locX, locY)
  25.     for x = locX, locX + model:getW() - 1 do
  26.         for y = locY, locY + model:getH() - 1 do
  27.             if not model_equals(-1, x, y) and not model_equals(model.index, x, y) then
  28.                 return false
  29.             end
  30.         end
  31.     end
  32.     return true
  33. end
  34.  
  35. -- -----------------------------------------------------------------
  36. local function tryPlace(data, place)
  37.     local locX = place.x
  38.     local locY = place.y
  39.  
  40.     result = false
  41.     if nil == data.closed[locX] then
  42.         data.closed[locX] = {}
  43.     end
  44.     if not data.closed[locX][locY] then
  45.         data.closed[locX][locY] = true
  46.         if isFreePlace(data.model, locX, locY) then
  47.             result = true
  48.         end
  49.     end
  50.     return result
  51. end
  52.  
  53. -- -----------------------------------------------------------------
  54. local function isInRect(x, y, w, h, destX, destY)
  55.     return x <= destX and destX < x + w and y <= destY and destY < y + h
  56. end
  57. -- -----------------------------------------------------------------
  58. function findDir(model, destX, destY)
  59.     -- Breadth-first search
  60.     -- Find starting dir to the destination
  61.     -- Return dir_no when there is no free path
  62.     local locX, locY = model:getLoc()
  63.     local w = model:getW()
  64.     local h = model:getH()
  65.  
  66.     if isInRect(locX, locY, w, h, destX, destY) then
  67.         return dir_no
  68.     end
  69.     if not model_equals(-1, destX, destY) then
  70.         return dir_no
  71.     end
  72.  
  73.     local data = {}
  74.     data.closed = {}
  75.     data.closed[locX] = {}
  76.     data.closed[locX][locY] = true
  77.     data.model = model
  78.  
  79.     local fifo = {}
  80.     table.insert(fifo, {dir=dir_left, x=locX - 1, y=locY})
  81.     table.insert(fifo, {dir=dir_right, x=locX + 1, y=locY})
  82.     table.insert(fifo, {dir=dir_up, x=locX, y=locY - 1})
  83.     table.insert(fifo, {dir=dir_down, x=locX, y=locY + 1})
  84.  
  85.     while table.getn(fifo) > 0 do
  86.         local place = table.remove(fifo, 1)
  87.         if tryPlace(data, place) then
  88.             if isInRect(place.x, place.y, w, h, destX, destY) then
  89.                 return place.dir
  90.             end
  91.  
  92.             table.insert(fifo, {dir=place.dir, x=place.x - 1, y=place.y})
  93.             table.insert(fifo, {dir=place.dir, x=place.x + 1, y=place.y})
  94.             table.insert(fifo, {dir=place.dir, x=place.x, y=place.y - 1})
  95.             table.insert(fifo, {dir=place.dir, x=place.x, y=place.y + 1})
  96.         end
  97.     end
  98.     return dir_no
  99. end
  100.  
  101.